/*******************************************************************************
 * Witz - Winboard Chess Engine                                                *
 * BOOK.C                                                                      *
 *                                                                             *
 * Handles generation and probing of opening books.                            *
 *                                                                             *
 * Please refer to the licence notice in MAIN.C                                *
 *                                                                             *
 * Copywright (C) 2006 Pradu Kannan                                            *
 * http://witz.sf.net/                                                         *
 ******************************************************************************/

#include "build.h"
#include "defs.h"
#include "protos.h"
#include "data.h"

//this file only contains private variables
FILE* book=NULL;

//the red-black tree
struct _rbTree
{
	rbNode* root;  //pointer to the root node
	int size;       //ponter to the number of elements
}rbTree;

/*createBook()
 *crates an opening book from pgn files
 *
 *argc - number of arguments
 *argv - arguments [exename, bookname, pgn1.pgn, pgn2.pgn, ... pgnN.pgn]
 */
void createBook(int argc, char *argv[])
{
	int i;
	int ply=0;
	pgnFile pgn;
	pgnPosition pgnPos;
	bookPosition bookPos;
	char bookLocation[512];


	//witz.exe makebook Example.wbk 20 Example.pgn
	initializeEngine();

	strcpy(bookLocation,argv[2]);
	if(sscanf(argv[3],"%d",&ply)<=0)
	{
		printf("Error, ply parameter (%s) is not an integer\n",argv[3]);
		return;
	}

	book=fopen(bookLocation, "wb+");
	if(book==NULL)
	{
		printf("Error, book file (%s) could not be created for readind and writing\n",bookLocation);
		return;
	}

	rbTree.size=0;
	rbTree.root=NULL;

	bookPos.numGames=2;

	for(i=4 ;i<argc;i++)
	{
		printf("\n%s\n",argv[i]);
		openPGN(&pgn, argv[i]);
		if(pgn.pointer==NULL) continue;
		while(!nextPosition(&pgn, &pgnPos))
		{
			//add to the red black tree
			bookPos.key=pgnPos.key;
			bookPos.results=pgnPos.result;
			rb_insert(&bookPos);

			if(ply>0 && pgn.ply>=ply)
				pgn.stage=PGN_STAGE_SEARCH;
		}
		closePGN(&pgn);
	}

	//write to book
	while(!rbGetLeast(rbTree.root,&bookPos))
	{
		if(fwrite(&bookPos,sizeof(bookPosition),1,book)<=0)
		{
			printf("Error Writing to a temporary file!\n");
			quit();
		}
	}
	fclose(book);
}

/*findInBook
 *finds a position in the book
 *
 *@param pos     - the position to search for
 *@param bookPos - the book position if found'
 *
 *@returns true if the position was found
 */
bool findInBook(board *pos, bookPosition *bookPos)
{
	long left,right,mid;
	if(book==NULL) openBook();
	fseek(book,0,SEEK_SET);
	left=ftell(book)/sizeof(bookPosition);
	fseek(book,0,SEEK_END);
	right=(ftell(book)-1)/sizeof(bookPosition);
	while(left<=right)
	{
		mid=(left+right)/2;
		fseek(book,mid*sizeof(bookPosition),SEEK_SET);
		if(fread(bookPos, sizeof(bookPosition), 1, book)!=1)
		{
			printf("Error reading from Book\n");
			closeBook();
			return false;
		}
		if(bookPos->key==pos->hashkey)
		{
			closeBook();
			return true;
		}
		if(pos->hashkey<bookPos->key)
			right=mid-1;
		else
			left=mid+1;
	}
	return false;
}

/*getBookMove()
 *gets a book move from the current state of the board
 *
 *@returns NULLMOVE if no book move is found;
 */
move getBookMove()
{
	board tempPos;
	bookPosition bookPos;
	int i, j, k, count=0, totalWeight;
	U32 maxNumGames=0, moves[512];
	double scores[512], totalScores=0;
	double randValue;
	bookPosition bookScores[512];
	bool printed[512];

	if(!(useBook && hasBook))
		return NULLMOVE;

	for(i=0;i<mainMoveList.moveCount;i++)
	{
		tempPos=mainboard;
		makemove(&tempPos,mainMoveList.moves[i].m);

		if(findInBook(&tempPos,&bookPos))
		{
			moves[count]=mainMoveList.moves[i].m;
			bookScores[count]=bookPos;
			if(bookPos.numGames>maxNumGames)
				maxNumGames=bookPos.numGames;
			count++;
		}
	}

	if(count==0) return NULLMOVE;
	if(count==1) return moves[0];

	//get percentages for each
	totalWeight=gamesWeight+winsWeight;
	for(i=0;i<count;i++)
	{
		scores[i]=(((double)(bookScores[i].numGames))/(double)maxNumGames)*((double)gamesWeight/totalWeight);
		scores[i]+=((double)(bookScores[i].results)/(double)bookScores[i].numGames)*((double)winsWeight/(double)totalWeight);
		totalScores+=scores[i];
	}

	if(book!=NULL) closeBook();

	//normalize each one
	for(i=0;i<count;i++)
		scores[i]/=totalScores;

	if(Post)
	{
		printf("0 0 0 0");
		//print moves in sorted order
		//very inefficient, but it really dosen't matter
		
		//initalize boolean array
		for(i=0;i<count;i++)
			printed[i]=false;

		//print largest values first
		for(i=0;i<count;i++)
		{
			randValue=0;
			
			for(j=0;j<count;j++)
			{
				if(printed[j]) continue;
				else if(scores[j]>randValue)
				{
					randValue=scores[j];
					k=j;
				}
			}
			
			printf(" %s(%.0f%%)",moveToSAN(&mainboard,moves[k]),100*scores[k]);
			printed[k]=true;

		}
		printf("\n");
	}
	if(ICS)
	{
		printf("tellothers Book Moves: ");

		for(i=0;i<count;i++)
			printed[i]=false;

		//print largest values first
		for(i=0;i<count;i++)
		{
			randValue=0;
			
			for(j=0;j<count;j++)
			{
				if(printed[j]) continue;
				else if(scores[j]>randValue)
				{
					randValue=scores[j];
					k=j;
				}
			}
			
			printf(" %s(%.0f%%)",moveToSAN(&mainboard,moves[k]),100*scores[k]);
			printed[k]=true;

		}
		printf("\n");
	}
	srand((unsigned)rand());
	randValue=rand()/((double)RAND_MAX);
	printf("%f\n",randValue);
	totalScores=0;
	for(i=0;i<count;i++)
	{
		totalScores+=scores[i];
		if(totalScores>=randValue) break;
	}
	if(i==count) return moves[i-1];
	else return moves[i];
}

/*openBook()
 *opens the opening book
 */
void openBook()
{
	if(hasBook)
	{
		book=fopen(bookPath,"rb");
		if(book==NULL) hasBook=false;
	}
}

/*closeBook()
 *closes the opening book
 */
void closeBook()
{
	if(book!=NULL)
	{
		fclose(book);
		book=NULL;
	}
}

/****************************INTERFACE TO PGN FILES****************************/

/*openPGN()
 *opens a pgn file
 *@param pgn  - the pgn file (must be a closed file)
 *@param path - path to the pgn file
 *
 *NOTE: openPGN does not guarentee that the pgn file is corretly initialized.
 *      If this information is necessary, determine if pgn->pointer is NULL
 */
void openPGN(pgnFile* pgn, char* path)
{
	pgn->pointer=fopen(path,"rt");
	if(pgn->pointer==NULL)
		printf("Can't open %s for reading\n",path);
	pgn->stage=PGN_STAGE_SEARCH;
	pgn->game=0;
}

/*closePGN()
 *closes a pgn file
 *@param pgn  - a pgn file
 */
void closePGN(pgnFile* pgn)
{
	if(pgn->pointer!=NULL) fclose(pgn->pointer);
}

/*nextPosition()
 *gets the next position from a pgn file
 *@param pgn    - the pgn file
 *@param pgnPos - the position that needs to be retrived from the pgn
 *
 *@returns true if nextPosition() is unable to get another position
 *
 *NOTE: nextPosition dosne't do perfect input validation but handles most
 *      errors
 *NOTE: THE PGN FILE CANNOT HAVE ANY RECURSIVE ANNOTATION VARIATIONS
 */
bool nextPosition(pgnFile* pgn, pgnPosition* pgnPos)
{
	//the following variables are used in search
	char token[512], tempChar, *tempPos;
	moveList moveChoices;
	bool read;
	int i,temp;
	size_t tempSize,temp2;

	//searching for a new game
	if(pgn->stage==PGN_STAGE_SEARCH)
	{
searchPGN:
		//search until you find a result tag
		while(pgn->stage==PGN_STAGE_SEARCH)
		{
			if(!fgets(pgn->line,512,pgn->pointer)) //if error in reading
				return true;
			if(!strncmp(pgn->line,"[Result \"0-1\"]",14))
				pgn->stage=PGN_STAGE_BLACK;
			else if(!strncmp(pgn->line,"[Result \"1-0\"]",14))
				pgn->stage=PGN_STAGE_WHITE;
			else if(!strncmp(pgn->line,"[Result \"1/2-1/2\"]",18))
				pgn->stage=PGN_STAGE_DRAW;
			//ignore games with no result -- [Result "*"]
		}
		pgn->game++;
		if(!(pgn->game&0xFF))
			printf("Progress: %d\n",pgn->game);
		//ignore all other tags and newlines
		for(;;)
		{
			if(!fgets(pgn->line,512,pgn->pointer)) //if error in reading
				return true;
			if(*(pgn->line)!='[' && *(pgn->line)!='\n')
				break;
		}
		pgn->pos=newBoard;
		pgn->ply=0;
	}

	//try to read a move
	for(;;)
	{
		read=false;
		*token='\0';
		//%[^) }\n] means read all charecters that are not newline, space, } or )
		//%[^]}\n] means read all charecters that are not newline, }, or )
		if((temp=sscanf(pgn->line,"%[^) }\n] %[^\n]",token,pgn->line))<2 || *token==';' || *token=='$')
		{
			*(pgn->line)='\0';
			//if nothing was read at all
			if(temp<=0)
				*token=';';
			//if game ended, start searching
			else if(*token=='\n' || !strcmp(token,"1-0") || !strcmp(token,"0-1") || !strcmp(token,"1/2-1/2"))
			{
				pgn->stage=PGN_STAGE_SEARCH;
				goto searchPGN;
			}
			read=true;
		}
		if(*token==';' || *token=='$' || *token=='}' || isdigit(*token));
		else if(*token=='{') //brace comment
		{
			//see if the } charecter is in the current line
			if((tempPos=strchr(pgn->line,'}'))!=NULL)
			{
				//} charecter was found
				tempSize=(int)(tempPos-pgn->line+1); //temp contains the amount to shift by
				//printf("line: %s\n",pgn->line);
				//printf("temp: %d\n",temp);
				temp2=strlen(pgn->line); //temp2 contains the length of the string
				//shift all the charecters down the string
				for(i=temp;((size_t)i)<=temp2;i++)
					pgn->line[i-tempSize]=pgn->line[i];
				continue;
			}
			do
				if((tempChar=fgetc(pgn->pointer))==EOF) return true;
			while(tempChar!='}');
			if((tempChar=fgetc(pgn->pointer))==EOF) return true;
			if(!isprint(tempChar))
			{
				if(ungetc(tempChar,pgn->pointer)) return true;
			}
			read=true;
		}
		else if(isalpha(*token)) //see if it is a move
		{
			//generate legal moves
			generateLegalMoves(&(pgn->pos), &moveChoices);
			//check if the first charecters of the input is a move in SAN
			for(i=0;i<moveChoices.moveCount;i++)
			{
				if(!strncmp(moveToSAN(&(pgn->pos), moveChoices.moves[i].m), token, strlen(moveToSAN(&(pgn->pos), moveChoices.moves[i].m)))
					|| !strncmp(moveToCBSAN(&(pgn->pos), moveChoices.moves[i].m), token, strlen(moveToCBSAN(&(pgn->pos), moveChoices.moves[i].m))))
				{
					if(!strcmp(moveToSAN(&(pgn->pos),moveChoices.moves[i].m),"O-O") && !strncmp(token,"O-O-O",5))
						continue;

					makemove(&(pgn->pos),moveChoices.moves[i].m);
					pgn->ply++;
					pgnPos->key=pgn->pos.hashkey;
					if(pgn->stage==PGN_STAGE_DRAW)  //drawn game
						pgnPos->result=1;
					else if(pgn->stage==PGN_STAGE_WHITE) //white won the game
					{
						if(pgn->pos.side==BLACK) pgnPos->result=2;
						else pgnPos->result=0;
					}
					else //black won the game
					{
						if(pgn->pos.side==WHITE) pgnPos->result=2;
						else pgnPos->result=0;
					}
					if(read)
					{
						if(!fgets(pgn->line,512,pgn->pointer)) //if error in reading
							return true;
					}
					return false;
				}
			}
			//illegal move
			printf("Illegal Move %s in game %d!\n",token,pgn->game);
			pgn->stage=PGN_STAGE_SEARCH;
			goto searchPGN;
		}
		else //unidentified token
		{
			pgn->stage=PGN_STAGE_SEARCH;
			goto searchPGN;
		}

		if(read)
		{
			if(!fgets(pgn->line,512,pgn->pointer)) //if error in reading
				return true;
		}
	}
}

/***************************RED-BLACK TREES FOR BOOK***************************/

/*rb_insert()
 *inserts a book position into the red-black tree
 */
void rb_insert(bookPosition* bookPos)
{
	rbNode* newNode;

	newNode=malloc(sizeof(rbNode));
	newNode->bookPos=*bookPos;
	newNode->left=NULL;
	newNode->right=NULL;
	newNode->parent=NULL;
	newNode->color=RED;

	if(rbTree.root==NULL)
	{
		rbTree.root=newNode;
		rbTree.size++;
	}
	//if the node was found through traversal, no need to verify the tree
	else if(bianaryInsert(rbTree.root, newNode)) return;

	//verify the tree
	rbVerify(newNode);
}

/*binaryInsert()
 *a binaray tree insertion of a node
 *NOTE: the red-black tree cannot be empty
 *
 *@paran root - the relative root node
 *@param node - the new node
 *
 *@returns true if the position was found in the tree through traversal
 */
bool bianaryInsert(rbNode* root, rbNode* node)
{
	if(root==NULL)
	{
		root=node;
		if(rbkey(root->parent)>rbkey(root))
			root->parent->left=root;
		else
			root->parent->right=root;
		rbTree.size++;
		return false;
	}
	if(rbkey(node)==rbkey(root))
	{
		root->bookPos.numGames+=node->bookPos.numGames;
		root->bookPos.results+=node->bookPos.results;
		return true;
	}
	if(rbkey(node)<rbkey(root))
	{
		node->parent=root;
		return bianaryInsert(root->left,node);
	}
	node->parent=root;
	return bianaryInsert(root->right,node);
}

/*rbVerify()
 *verify's the red-black tree
 *
 *@param n - the node that was just inserted
 */
void rbVerify(rbNode* n)
{
	//The new node is at the root of the tree
	if(n->parent==NULL)
	{
		n->color=BLACK;
		return;
	}

	//The new node's parent is black
	if(n->parent->color==BLACK) return;

	//If both the parent and the uncle are red,
	//repaint them both black and repaint the grandparent red
	//treat the grandparent as the new node now
	if(uncle(n)!=NULL && uncle(n)->color==RED)
	{
		n->parent->color=BLACK;
		uncle(n)->color=BLACK;
		grandparent(n)->color=RED;
		rbVerify(grandparent(n));
		return;
	}

	if(n==n->parent->right && n->parent==grandparent(n)->left)
	{
		rb_rotateLeft(n->parent);
		if(n->left==NULL)
			printf("Error Emminent Stage 2\n");
		n=n->left;
	}
	else if(n==n->parent->left && n->parent==grandparent(n)->right)
	{
		rb_rotateRight(n->parent);
		if(n->right==NULL)
			printf("Error Emminent Stage 2\n");
		n=n->right;
	}

	n->parent->color=BLACK;
	grandparent(n)->color=RED;
	if(n==n->parent->left && n->parent==grandparent(n)->left)
		rb_rotateRight(grandparent(n));
	else rb_rotateLeft(grandparent(n));
}

/*rb_rotateLeft()
 *rotates the red-black tree at a node left
 *
 *    n               C
 *   / \             / \
 *  /   \           /   \
 * A     C   --->  n     D
 *      / \       / \
 *     B   D     A   B
 *
 *@param n - the pivot of rotation
 */
void rb_rotateLeft(rbNode* n)
{
	n->right->parent=n->parent;
	if(n->parent!=NULL)
	{
		if(n->parent->right==n)
			n->parent->right=n->right;
		else n->parent->left=n->right;
	}
	else
		rbTree.root=n->right;
	n->parent=n->right;
	n->right=n->parent->left;
	if(n->right!=NULL) n->right->parent=n;
	n->parent->left=n;
	//printf("RotL\n");
}

/*rb_rotateRight()
 *rotates the red-black tree at a node right
 *
 *      n            B
 *     / \          / \
 *    /   \        /   \
 *   B     D ---> A     n
 *  / \                / \
 * A   C              C   D
 *
 *@param n - the pivot of rotation
 */
void rb_rotateRight(rbNode* n)
{
	n->left->parent=n->parent;
	if(n->parent!=NULL)
	{
		if(n->parent->left==n)
			n->parent->left=n->left;
		else n->parent->right=n->left;
	}
	else
		rbTree.root=n->left;
	n->parent=n->left;
	n->left=n->parent->right;
	if(n->left!=NULL) n->left->parent=n;
	n->parent->right=n;
	//printf("RotR\n");
}

/*rbGetLeast()
 *get the smallest bookPosition in the red-black tree and deletes it
 *from the tree without verification
 *
 *@param n       - should be called with rbTree.root
 *@param bookPos - the pointer to the book Position
 *
 *@returns true if the tree is empty
 */
bool rbGetLeast(rbNode* n, bookPosition* bookPos)
{
	if(n==NULL) return true;
	while(n->left!=NULL) n=n->left;
	*bookPos=n->bookPos;
	if(n->right!=NULL)
	{
		//if the node is the root node
		if(n->parent==NULL)
		{
			rbTree.root=n->right;
			rbTree.root->parent=NULL;
		}
		else
		{
			n->parent->left=n->right;
			n->right->parent=n->parent;
		}
	}
	else
	{
		if(n->parent==NULL) rbTree.root=NULL;
		else n->parent->left=NULL;
	}
	//free the pointer
	free(n);
	//n=NULL;
	return false;
}
